Generating Permutations Recursively

Algorithmics 2025

The Problem

We want to generate all permutations of a list (e.g. [B, C, D]).

Recursive Strategy

At position k, decide which element should go there.
Swap it into position.
Recurse to fill the next position k+1.
When k = n (last index), we have a complete permutation.
Backtrack: swap back and try the next option.

Pseudocode

Procedure Permute(list, k, n):
    if k = n then
        output list
    else
        For i from k to n do
            swap(list[k], list[i])
            Permute(list, k+1, n)
            swap(list[k], list[i])   // backtrack
        EndFor

Example Walkthrough

List = [B, C, D], start with k = 0, n = 2

Fix B first → recurse on [C, D]
- Output [B, C, D]
- Output [B, D, C]
Fix C first → recurse on [B, D]
- Output [C, B, D]
- Output [C, D, B]
Fix D first → recurse on [C, B]
- Output [D, C, B]
- Output [D, B, C]

Outputs

All 6 permutations are produced:

[B, C, D]
[B, D, C]
[C, B, D]
[C, D, B]
[D, C, B]
[D, B, C]

Key Ideas

k = current index we’re filling
n = last index
Recursive calls explore all options.
Backtracking ensures the list is restored after each branch.